package io.github.hadyang.leetcode.bytedance;

import java.util.HashSet;
import java.util.Set;

/**
 * 最长连续序列 给定一个未排序的整数数组，找出最长连续序列的长度。
 *
 * <p>要求算法的时间复杂度为 O(n)。
 *
 * <p>示例:
 *
 * <p>输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
 *
 * @author haoyang.shi
 */
public class Array1019 {

  public static int longestConsecutive(int[] nums) {
    if (nums.length <= 1) {
      return nums.length;
    }

    Set<Integer> set = new HashSet<>();

    for (int num : nums) {
      set.add(num);
    }

    int pre, after, max = 0;
    for (int num : nums) {
      int temp = 1;
      set.remove(num);

      pre = num;
      after = num;

      while (set.contains(--pre)) {
        temp++;
        set.remove(pre);
      }

      while (set.contains(++after)) {
        temp++;
        set.remove(after);
      }

      max = Math.max(max, temp);
      if (max > nums.length / 2) {
        return max;
      }
    }

    return max;
  }

  public static void main(String[] args) {
    System.out.println(longestConsecutive(new int[] {100, 4, 200, 1, 3, 2}));
  }
}
